package leetcode.editor.cn;

import java.util.PriorityQueue;
import java.util.Scanner;

/**
题目名字---:删除链表的倒数第 N 个结点
题目编号---:19	
解题时间---:2021-12-02 09:36:49
*/

public class RemoveNthNodeFromEndOfList{
    public static void main(String[] args) {
        Solution solution = new RemoveNthNodeFromEndOfList().new Solution();
        ListNode head = create();
//        sortList(head);
        ListNode listNode = sortList1(head);
        System.out.println();
    }
    public static ListNode create() {
        ListNode  head = new ListNode(Integer.MIN_VALUE);
        Scanner scanner = new Scanner(System.in);
        System.out.println("input");
        int i = scanner.nextInt();
        while (i!=-1) {
            ListNode node = new ListNode(i);
            node.next  = head.next;
            head.next = node;
            System.out.println("input");
            i=scanner.nextInt();
        }
        return head.next;
    }
    public static ListNode sortList(ListNode head) {
        ListNode sentinel = new ListNode(Integer.MIN_VALUE);
        sentinel.next = head;
        for (ListNode i =sentinel.next;i!=null;i=i.next) {
            for (ListNode j=i;j!=null;j=j.next) {
                int valI = i.val;
                int valJ = j.val;
                if (valI>valJ) {
                    i.val = valJ;
                    j.val = valI;
                }
            }
        }
        return sentinel.next;
    }

    /**
     * 使用最小堆的方式对链表排序
     * @param head
     * @return
     */
    public static ListNode sortList1(ListNode head) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<ListNode>((s1,s2)->{
            return Integer.compare(s1.val,s2.val);
        });
        while (head!=null){
            priorityQueue.offer(head);
            head =  head.next;
        }
        ListNode sentinel = new ListNode(Integer.MIN_VALUE);
        ListNode curr =sentinel;
        while (priorityQueue.size()>0) {
            ListNode node = priorityQueue.poll();
            curr.next = node;
            curr = curr.next;
        }
        return sentinel.next;
    }

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    /**
     * @param head  头结点
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(Integer.MIN_VALUE);
        sentinel.next = head; //哨兵节点
        ListNode first = sentinel,second = sentinel;
        for (int i = 0; i < n; i++) {
            first = first.next;  // n<=链表长度
        }
        while (first.next!=null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return sentinel.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}